package offerbook;

import utils.ListNode;

import java.util.ArrayList;

/**
 * 给一个单向链表，从尾到头输出。
 *
 * @date 2020/3/7 22:42
 */
public class Code05_PrintListTailToHead {
    /**
     * 方式1：正向遍历用栈或数组存储，然后pop或逆序输出。
     * 时空都是O(n)，略。
     */
    //方式2：利用递归栈
    public static void reversePintLink2(ListNode head) {
        if (head == null)  return;
        reversePintLink2(head.next);
        System.out.print(head.val + " ");
    }

    /**
     * 方式3：翻转链表，然后输出。注意最后再翻转回去
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null) return new ArrayList<>();
        ListNode pre = null;
        ListNode p = listNode;
        while (p != null) {
            ListNode next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        ArrayList<Integer> res = new ArrayList<>();
        //pre is the tail and also the head
        p = pre;
        pre = null;
        //边遍历，边翻转
        while (p != null) {
            res.add(p.val);
            ListNode next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        return res;
    }
}
